package com.likeycy.my.sort.cmp;

/**
 * @ClassName: QuickSort
 * @Description: 快速排序：重点！！！
 * @Author: sodagreen
 * @Date: 2021/4/3 7:55
 * @Version: 1.0
 */
public class QuickSort<T extends Comparable<T>> extends Sort<T> {

    @Override
    protected void sort() {
        sort(0, array.length);
    }

    /**
     * 对 [begin, end) 范围的元素进行快速排序
     */
    private void sort(int begin, int end) {
        if (end - begin < 2) {
            return;
        }

        // 确定轴点元素位置
        int mid = pivotIndex(begin, end);
        // 对子序列进行快速排序
        sort(begin, mid);
        sort(mid + 1, end);
    }

    /**
     * 构造出 [begin, end) 范围的轴点元素
     * @return 轴点元素的最终位置
     */
    private int pivotIndex(int begin, int end) {
        // 为了防止最坏情况，随机选择轴点元素
        swap(begin, begin + (int) (Math.random() * (end - begin)));

        // 备份 begin 位置的元素
        T pivot = array[begin];
        // end 指向最后一个元素
        end--;
        while (begin < end) {

            // 从右往左扫描遍历
            while (begin < end) {
                // 右边元素 > 轴点元素
                if (comparatorToElements(pivot, array[end]) < 0) {
                    end--;
                } else {
                    // 来到 else 代表右边元素 <= 轴点元素。结束内循环，从另一侧开始扫描
                    array[begin++] = array[end];
                    break;
                }
            }

            // 从左边往右边遍历扫描
            while (begin < end) {
                // 左边元素 > 轴点元素
                if (comparatorToElements(pivot, array[begin]) > 0) {
                    begin++;
                } else {
                    // 来到 else 表示 左边元素 >= 轴点元素
                    array[end--] = array[begin];
                    // 结束内循环换另一边扫描
                    break;
                }
            }
        }

        // 将轴点元素放入最终的位置
        array[begin] = pivot;
        // 返回轴点元素的位置
        // begin==end
        return begin;
    }
}
